The present invention is related to the field of task scheduling for multiprocessing computerized systems.
Many computerized systems are of the “multiprocessing” variety in which the processing workload of the system is distributed across two or more relatively independent processors. Modern semiconductors are sufficiently dense that multiple processor “cores”, such as PowerPC® general-purpose processors, can be placed in a single integrated circuit and used in a variety of applications. As an example, multiple-processor complexes are utilized to perform a variety of functions in front-end and back-end interface modules of data storage systems such as those sold by EMC Corporation under the trademark Symmetrix®.
In computerized systems generally, the workload typically consists of a number of distinct “processes”. In general-purpose computer systems, there may be processes for performing various system tasks such as handling network communications, memory management, etc, as well as processes that are associated with user applications (e.g., one or more processes that instantiate a database application or Web server). The process paradigm is also used in so-called embedded computerized systems used within larger systems having particular applications. The above-referenced processing complexes of a data storage system such as Symmetrix system are examples of embedded computerized systems.
Multiprocessing systems can be classified as either “symmetric” or “asymmetric” based on how the processing workload is distributed among the processors. In asymmetric multiprocessing systems, processes are generally assigned to certain processors only. Asymmetric multiprocessing approaches are commonly used in embedded computerized systems, in which it may be convenient to partition the overall workload into some small number of pieces and assign them to separate processors. In one example, interface modules of Symmetrix data storage systems have utilized one processor for communicating with external host computers that are clients of the storage system, and another processor for communicating with the back-end disk drives on which data is stored. In asymmetric multiprocessing systems, each processor is responsible for its own process scheduling. There is generally no need for scheduling at a higher (inter-processor) level because processes are constrained to be executed on particular processors.
In contrast to asymmetric multiprocessing systems, symmetric multiprocessing systems generally allow for processes to be executed on any processor. The processors can be seen as resources that are utilized as needed to carry out the overall processing workload of the system. Thus, in symmetric multiprocessing systems it is an aspect of the scheduler to consider the relative capabilities and loading of the processors, for example, in making scheduling decisions and assigning processes to processors.
In multiprocessing systems including symmetric multiprocessing systems, it is known to organize the scheduler in an asymmetric fashion as one master scheduler executing on one processor and a set of sub-schedulers executing on the other processors. In one configuration, the master scheduler communicates with and controls the operation of the sub-schedulers to carry out one coherent scheduling algorithm for the overall computerized system. Thus the respective operations of the master scheduler and sub-schedulers are synchronized sufficiently to enable such communication and control.